\section{Subquadratic time offline token-forwarding algorithms}
\label{sec:centralized}
We give two centralized algorithms for the $k$-gossip problem in the
offline model: an $O(\min\{n\sqrt{k\log n}, nk\})$ round algorithm in
Section \ref{sec:upper}, and a bicriteria {$\rb{O(n^\epsilon), O(\log
    n)}$-approximation} algorithm in Section \ref{sec:approx}.\junk{,
  which means if $L$ is the number of rounds needed by an optimal
  algorithm where one token is broadcast by every node per round, then
  our approximation algorithm will complete in $O(n^\epsilon L)$
  rounds and the number of tokens broadcast by any node is $O(\log n)$
  in any given round.} Both algorithms use a leveled graph constructed
from the sequence of dynamic graphs which we call the {\em
  evolution graph}.  Appendix~\ref{app:centralized} describes this
construction and contains all omitted proofs.

\begin{lemma}
\label{lem:level.steiner}
Let there be $k$ tokens, each with a source and a set of
destinations. It is feasible to send all the tokens to all of their
destinations using $l$ rounds, where every node broadcasts only one
token in each round, iff $k$ directed Steiner trees can be packed in
the corresponding evolution graph with $2l + 1$ levels, one for each
token with its root being the copy of the source at level $0$ and its
terminals being the copies of the destinations at level $2l$.
\end{lemma}

\input{flow_based_full}
\input{approx_full}
